package com.programmercarl.list;

/**
 * https://leetcode.cn/problems/design-linked-list/description/
 *
 * @author yulongtian
 * @create 2024-12-12 23:55
 */
public class Test01 {
    public static void main(String[] args) {
        Test01 test01 = new Test01();
        test01.test();
    }

    private void test() {
//        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtHead(1);
//        myLinkedList.addAtTail(3);
//        myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
//        System.out.println(myLinkedList.get(1));              // 返回 2
//        myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
//        System.out.println(myLinkedList.get(1));              // 返回 3
//        System.out.println();
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtTail(1);
        myLinkedList.get(0);
    }

    class Node {
        int data;
        Node next;

        public Node() {

        }

        public Node(int data) {
            this.data = data;
        }

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    class MyLinkedList {
        Node head;
        int len;

        public MyLinkedList() {
            len = 0;
        }

        public int get(int index) {
            if (index < 0 || index >= len) {
                return -1;
            }
            Node temp = head;
            while (index > 0) {
                temp = temp.next;
                index--;
            }
            return temp.data;
        }

        public void addAtHead(int val) {
            if (len == 0) {
                head = new Node(val);
                len += 1;
                return;
            }
            Node newNode = new Node(val);
            newNode.next = head;
            head = newNode;
            len += 1;
        }

        public void addAtTail(int val) {
            if (len == 0) {
                head = new Node(val);
                len += 1;
                return;
            }
            Node point = head;
            while (point.next != null) {
                point = point.next;
            }
            point.next = new Node(val);
            len += 1;
        }

        public void addAtIndex(int index, int val) {
            if (index < 0 || index > len) {
                return;
            }
            if (index == 0) {
                addAtHead(val);
                return;
            }
            if (index == len) {
                addAtTail(val);
                return;
            }
            Node point = head;
            Node pre = head;
            for (int i = 0; i < index; i++) {
                pre = point;
                point = point.next;
            }
            Node newNode = new Node(val);
            pre.next = newNode;
            newNode.next = point;
            len += 1;
        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index >= len) {
                return;
            }
            if (index == 0) {
                head = head.next;
                len -= 1;
                return;
            }
            Node point = head;
            Node pre = head;
            for (int i = 0; i < index; i++) {
                pre = point;
                point = point.next;
            }
            if (point.next == null) {
                //最后一个节点
                pre.next = null;
            } else {
                pre.next = point.next;
            }
            len -= 1;
        }
    }

}
